package org.example.ch14;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/word-ladder/
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
 *
 * 序列中第一个单词是 beginWord 。
 * 序列中最后一个单词是 endWord 。
 * 每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典 wordList 中的单词。
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
 * 找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
 *
 */
public class LadderLength {

    /**
     * beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
     *
     * @param args
     */
    public static void main(String[] args) {
        LadderLength ladder = new LadderLength();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList<String>(Arrays.asList("hot","dot","dog","lot","log","cog"));
        int result=ladder.ladderLength(beginWord,endWord,wordList);
        System.out.println(result);
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList__){
        Set<String> wordList = new HashSet<String>(wordList__);
        Set<String> beginSet = new HashSet<String>(),endSet = new HashSet<String>();
        int len = 1;
        int strLen = beginWord.length();
        HashSet<String> visited = new HashSet<String>();

        beginSet.add(beginWord);
        endSet.add(endWord);
        //BFS starts here
        while (!beginSet.isEmpty() && !endSet.isEmpty()){
            if(beginSet.size() > endSet.size()){
                Set<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }
            Set<String> temp = new HashSet<String>();
            for (String word:beginSet){
                char[] chs = word.toCharArray();
                for (int i = 0; i < chs.length; i++) {
                    for (char c= 'a';c<='z';c++){
                        char old = chs[i];
                        chs[i] = c;
                        String target = String.valueOf(chs);
                        if(endSet.contains(target)){
                            return len+1;
                        }

                        if(!visited.contains(target)&& wordList.contains(target)){
                            temp.add(target);
                            visited.add(target);
                        }
                        chs[i] = old;
                    }
                }
            }
            beginSet = temp;
            len++;
        }
        return 0;
    }

}
